package leet39combinationsum

import "sort"

func CombinationSum(candidates []int, target int) [][]int {
	// 思路：
	// 将candidates排一下序，按照从大到小排序，方便后续取值
	// 将添加组合元素的方法抽象为一个统一的子问题：即
	// 遍历从小到大的集合(每次的遍历的其实是一个子集)，遍历到的元素其实在不断的添加到目标组合中，直到剩余和小于0，如果剩余和恰好为0的话则添加到目标集合中。
	// 当目标组合的剩余和小于0或者等于0，就要返回上一层递归栈了，在上一层递归栈中将刚才添加进去的元素弹出，
	// 然后尝试放入一个稍微更小一点的元素（这个操作其实就是重新进入子问题之中了）
	sort.Slice(candidates, func(i, j int) bool {
		return candidates[i] > candidates[j]
	})
	result := [][]int{}
	path := []int{}
	var backtrack func(start int, leftSum int)
	backtrack = func(start int, leftSum int) {
		if leftSum == 0 {
			// path因为是共用的，所以此处append的时候一定要拷贝一份出来，避免后续的
			pathCopy := make([]int, len(path))
			copy(pathCopy, path)
			result = append(result, pathCopy)
			return
		}
		if leftSum < 0 {
			return
		}
		for i := start; i < len(candidates); i++ {
			path = append(path, candidates[i])
			// 同一个数可以被不断的添加到目标组合之中
			// 所以我们要决定是继续backtrack(i)呢还是backtrack(i+1)
			// 决定的判断要依赖于新的剩余和了，如果新的剩余和小于0了，就意味着当前元素不太合适了，得找一个更小的了
			newLeftSum := leftSum - candidates[i]
			if newLeftSum < 0 {
				backtrack(i+1, newLeftSum)
			} else {
				backtrack(i, newLeftSum)
			}
			// 回退一格
			path = path[:len(path)-1]
		}
	}

	backtrack(0, target)
	return result
}
